public class Solution906 {
    public int superpalindromesInRange(String left, String right) {
        long a=Long.parseLong(left);
        long b=(long)Math.sqrt(a);
        if (b*b<a){
            b++;
        }
        long c=Long.parseLong(right);
        long d=(long)Math.sqrt(c);
        if (!isHuiwen(b)){
            b=next((int)b);
        }
        int ans=0;
        for (int i=(int)b;i<=d;i=next(i)){
            long t=(long)i*i;
            if (isHuiwen(t)){
                ans++;
            }
        }
        return ans;
    }

    private int next(int n) {
        String s=String.valueOf(n);
        StringBuilder stringBuilder1=new StringBuilder(s.substring(0,s.length()/2));
        StringBuilder stringBuilder2=new StringBuilder(stringBuilder1).reverse();
        if (s.length()%2==1){
            stringBuilder1.append(s.charAt(s.length()/2));
        }
        int t=Integer.parseInt(stringBuilder1.append(stringBuilder2).toString());
        if (t>n){
            return t;
        }
        if (s.length()%2==1){
            String r=s.substring(0,s.length()/2+1);
            int p=Integer.parseInt(r);
            p++;
            StringBuilder stringBuilder3=new StringBuilder(String.valueOf(p));
            if (String.valueOf(p).length()==r.length()){
                StringBuilder stringBuilder4=new StringBuilder(stringBuilder3);
                stringBuilder4.deleteCharAt(stringBuilder4.length()-1).reverse();
                return Integer.parseInt(stringBuilder3.append(stringBuilder4).toString());
            }else{
                stringBuilder3.deleteCharAt(stringBuilder3.length()-1);
                StringBuilder stringBuilder4=new StringBuilder(stringBuilder3).reverse();
                return Integer.parseInt(stringBuilder3.append(stringBuilder4).toString());
            }
        }else{
            String r=s.substring(0,s.length()/2);
            int p=Integer.parseInt(r);
            p++;
            StringBuilder stringBuilder3=new StringBuilder(String.valueOf(p));
            StringBuilder stringBuilder4;
            if (String.valueOf(p).length()==r.length()){
                stringBuilder4 = new StringBuilder(stringBuilder3).reverse();
            }else{
                stringBuilder4 = new StringBuilder(stringBuilder3);
                stringBuilder4.deleteCharAt(stringBuilder4.length()-1).reverse();
            }
            return Integer.parseInt(stringBuilder3.append(stringBuilder4).toString());
        }
    }

    private boolean isHuiwen(long n) {
        String s=String.valueOf(n);
        for (int i=0,j=s.length()-1;i<j;i++,j--){
            if (s.charAt(i)!=s.charAt(j)){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new Solution906().superpalindromesInRange("4","1000"));
    }
}
